public class LeetCode695 {

    public static void main(String[] args) {

        System.out.println(maxAreaOfIsland(new int[][]{
                {0,0,1,0,0,0,0,1,0,0,0,0,0},
                {0,0,0,0,0,0,0,1,1,1,0,0,0},
                {0,1,1,0,1,0,0,0,0,0,0,0,0},
                {0,1,0,0,1,1,0,0,1,0,1,0,0},
                {0,1,0,0,1,1,0,0,1,1,1,0,0},
                {0,0,0,0,0,0,0,0,0,0,1,0,0},
                {0,0,0,0,0,0,0,1,1,1,0,0,0},
                {0,0,0,0,0,0,0,1,1,0,0,0,0},
        }));

        System.out.println(maxAreaOfIsland(new int[][]{
                {0,0,0,0,0,0,0,0}
        }));

    }

    public static int maxAreaOfIsland(int[][] grid) {
        int max = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    max = Math.max(max, dfsGrid(grid, i, j));
                }
            }
        }

        return max;
    }

    private static int dfsGrid(int[][] grid, int sr, int sc) {
        if (sr < 0 || sc < 0 || sr >= grid.length || sc >= grid[sr].length || grid[sr][sc] != 1) {
            return 0;
        }

        int count = 1;
        grid[sr][sc] = 2;

        count += dfsGrid(grid, sr + 1, sc);
        count += dfsGrid(grid, sr - 1, sc);
        count += dfsGrid(grid, sr, sc + 1);
        count += dfsGrid(grid, sr, sc - 1);
        return count;
    }
}
